#include <iostream>   
#include <climits>
#include "coin.h"  
using namespace std;  
  
int main()  
{  
    int c[4] = {0,0,0,0};
    int n;  
    cout << "请输入1,5,10,25美分分别的硬币数量: ";    
    cin >> c[0] >> c[1] >> c[2] >> c[3];   
    cout << "请输入总金额数（美分）: ";   
    cin >> n;  
      
    vector<int> coins = {1, 5, 10, 25}; // 硬币的面额  
    vector<int> dp(n + 1, INT_MAX); // 初始化 dp 数组，INT_MAX 表示不可达，存金额为i时的最小硬币数 
    vector<vector<int>> matrix(n+1, vector<int>(4, 0)); // 硬币数最小情况下各个面额硬币所剩下个数
    for(int i = 0; i < n+1; i++)
    {
        for(int t = 0; t < 4; t++)
        matrix[i][t] = c[t];
    }
    dp[0] = 0; // 0美分不需要硬币
    for (int i = 1; i <= n; i++) {  
        for (int j = 0; j < 4; j++) {  
            if (i >= coins[j] && matrix[i - coins[j]][j] > 0 && dp[i - coins[j]] != INT_MAX && dp[i] > dp[i - coins[j]] + 1) 
            {  
                dp[i] =  dp[i - coins[j]] + 1; // 更新最小硬币数量  
                matrix[i][j] = matrix[i - coins[j]][j] - 1;// 更新最小情况下各硬币种类还剩下的个数
            }  
        }  
    }  
      
    if (dp[n] == INT_MAX) {  
        cout << "无法凑出该金额" << endl;  
    } else {  
        cout << "最少需要 " << dp[n] << " 枚硬币" << endl; 
    }    
}  